package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 普通数组<br>
 * 数组、排序<br>
 * 中等
 *
 * <h1>56. 合并区间</h1>
 *
 * <p>给以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。</p>
 */
public class E14Merge {
    public static void main(String[] args) {
        E14Merge merge = new E14Merge();

        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        TimeCostUtil.timeCost("排序", () -> merge.solution1(intervals));
        // TimeCostUtil.timeCost("力扣-久处仍怦然.", () -> merge.solution2(intervals));

        List<int[]> ints = new ArrayList<>();
        for (int i = -1000000; i < 1000000; i++) {
            ints.add(DataGeneratorUtil.generateRandomIntArray(2, i, i + 10));
        }
        int[][] intervalArray = ints.toArray(new int[ints.size()][]);
        TimeCostUtil.timeCost("排序", () -> merge.solution1(intervalArray));
        TimeCostUtil.timeCost("排序", () -> merge.solution1_1(intervalArray));
        // TimeCostUtil.timeCost("力扣-久处仍怦然.", () -> merge.solution2(intervalArray));

    }

    // 排序
    public int[][] solution1(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    public int[][] solution1_1(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return intervals;
        }
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > end) {
                res.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            } else {
                end = Math.max(end, intervals[i][1]);
            }
        }
        res.add(new int[]{start, end});
        return res.toArray(new int[res.size()][]);
    }

    /**
     * 如果这题不是连续区间，而是整数区间，那么很容易想到维护一个最大长度的Boolean数组flag（题目限制不超过10000），遍历一遍intervals并给所有出现的区间，从start到end 的 flag[i]值赋true，最后遍历flag，统计连续为true的作为一个个区间。<br>
     * <p>
     * 但是提交算法发现不通过，如[[1,4],[5,6]]，正确结果是[[1,4],[5,6]]，我们的算法输出[1,6]，这是因为我们是整数区间，他会连接两个区间。<br>
     * <p>
     * 解决办法就是我们让flag数组长度乘2，赋值时对应值也乘2，这样做的好处是，如上个案例，[1,4]->[2,8]，[5,6]->[10,12]，中间就会出现断点9未被赋值，从而打破了两个区间不连续的问题。<br>
     *
     * @param intervals
     * @return
     */
    public int[][] solution2(int[][] intervals) {
        int n = intervals.length;
        int maxLen = 10001 * 2;//flag数组长度，二倍范围
        boolean[] flag = new boolean[maxLen];
        int max = -1;
        for (int i = 0; i < n; ++i) {
            max = max < intervals[i][1] * 2 + 1 ? intervals[i][1] * 2 + 1 : max;
            for (int j = intervals[i][0] * 2; j <= intervals[i][1] * 2; ++j) {
                flag[j] = true;
            }
        }

        List<int[]> list = new ArrayList<>();
        int index = 0;
        while (index < max) {
            int[] arr = new int[2];
            while (index < maxLen && flag[index] == false) ++index;
            if (index >= maxLen) break;
            arr[0] = index / 2;
            while (index < maxLen && flag[index] == true) ++index;
            arr[1] = (index - 1) / 2;
            list.add(arr);
        }
        return list.toArray(new int[list.size()][]);
    }
}
